package _18_剑指OfferII;

import java.util.PriorityQueue;
import java.util.Random;

public class _076_剑指OfferII数组中的第k大的数字 {

    public static void main(String[] args) {

        _076_剑指OfferII数组中的第k大的数字 v = new _076_剑指OfferII数组中的第k大的数字();


        int[] ins = {3, 2, 1, 5, 6, 4};
        System.out.println(v.findKthLargest(ins, 2));

    }

    // 快速排序，快速排序, 实际在划分的时候采用的是一种偏序思想，借鉴这个可以完成任务
    public int findKthLargest(int[] nums, int k) {

        return findKthLargest(nums, 0, nums.length - 1, k - 1);
    }

    private int findKthLargest(int[] nums, int start, int end, int k) {
        // 构建轴点
        int h = pivotIndex(nums, start, end);
        if (h == k) {
            return nums[h];
        }
        return h > k? findKthLargest(nums, start, h - 1, k): findKthLargest(nums, h + 1, end, k);
    }

    private int pivotIndex(int[] nums, int start, int end) {
        // 随机化比较函数
        random(nums, start, end);
        int v = nums[start];

        // 大的在左边，小的在右边
        while (start < end) {
            while (start < end) {
                if (nums[end] < v) {
                    end--;
                } else {
                    nums[start++] = nums[end];
                    break;
                }
            }
            while (start < end) {
                if (nums[start] > v) {
                    start++;
                } else {
                    nums[end--] = nums[start];
                    break;
                }
            }
        }
        nums[start] = v;
        return start;
    }

    private void random(int[] nums, int start, int end) {
        int index = new Random().nextInt(end - start + 1) + start;
        int temp = nums[start];
        nums[start] = nums[index];
        nums[index] = temp;
    }

    // Topk问题
    public int findKthLargest1(int[] nums, int k) {
        PriorityQueue<Integer> minQueue = new PriorityQueue<>();
        for (int num : nums) {
            if (minQueue.size() >= k) {
                if (num > minQueue.peek()) {
                    minQueue.poll();
                    minQueue.add(num);
                }
            }
            minQueue.add(num);
        }
        return minQueue.peek();
    }

}
